package com.example.algorithm.test;

import org.junit.Test;

/**
 * 链表反转-迭代
 * @author ljw
 * @date 2024-03-05 22:20
 */
public class ReverseList {

    static class ListNode {
        int val;
        ListNode next;

        public ListNode (int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /** 迭代方式反转  */
    public ListNode iterate(ListNode head) {
        ListNode preNode = null, nextNode;
        ListNode curNode = head;
        while (null != curNode) {
            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }

    @Test
    public void iterateTests() throws Exception{
        ListNode listNode5 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode headNode = iterate(listNode1);
        System.out.println(headNode.val);
    }


    /** 递归方式反转  */
    public ListNode recursion(ListNode curNode) {
        if (null == curNode || null == curNode.next) {
            //返回最后一个元素
            return curNode;
        }
        //从尾部往前处理
        ListNode new_head =recursion(curNode.next);
        // 分解为性质相同的小问题
        curNode.next.next = curNode;
        curNode.next = null;
        return new_head;
    }

    @Test
    public void recursionTests() throws Exception{
        ListNode listNode5 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode headNode = recursion(listNode1);
        System.out.println(headNode.val);
    }
}
